package leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-30 16:41
 **/
public class LeetCode378 {
    //归并排序
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[0] - y[0]);
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 1; i < k; i++) {
            int[] temp = queue.poll();
            if (temp[2] + 1 < n) {
                queue.offer(new int[]{matrix[temp[1]][temp[2] + 1], temp[1], temp[2] + 1});
            }
        }
        return queue.poll()[0];
    }

    //直接排序
    /*public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int[] arr = new int[n * n];
        int index = 0;
        for (int[] ints : matrix) {
            for (int anInt : ints) {
                arr[index++] = anInt;
            }
        }
        Arrays.sort(arr);
        return arr[k - 1];
    }*/

    //优先队列
    /*public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int i1 = 0; i1 < n; i1++) {
                queue.offer(matrix[i][i1]);
            }
        }
        for (int i = 1; i < k; i++) {
            queue.poll();
        }
        return queue.poll();
    }*/

}
